package com.example.question.dp.dp1;

import java.util.HashMap;
import java.util.Map;

/**
 * @Date 2023-07-18
 * @Author Jonathan
 * 动态规划：记忆化搜索
 * 动态规划解题的四个步骤:
 * 1.定义数组【状态数组】 用dp来表示
 * 2.状态初始化
 * 3.状态转移
 * 4.返回最终的需要的状态值
 */
public class Code01_Fib {
    public static void main(String[] args) {
        Code01_Fib fib = new Code01_Fib();
        new Thread(() -> {
            long l = System.currentTimeMillis();
            fib.fib1(50);
            System.out.println("fib.fib1(50) = " + (System.currentTimeMillis() - l));
        }).start();
        new Thread(() -> {
            long l = System.currentTimeMillis();
            fib.fib2(50, new HashMap<>());
            System.out.println("fib.fib2(50, new HashMap<>()) = " + (System.currentTimeMillis() - l));
        }).start();
    }


    public int fib(int n) {
        return fib2(n, new HashMap<>());
    }

    /**
     * 记忆化搜索
     * 自顶向下  还可以自底向上【迭代的写法】
     */
    public int fib2(int n, Map<Integer, Integer> cache) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        // 从缓存中获取
        if (cache.containsKey(n)) {
            return cache.get(n);
        }

        int left = fib2(n - 1, cache);
        int right = fib2(n - 2, cache);

        // 加入缓存
        cache.put(n - 1, left);
        cache.put(n - 2, right);

        return left + right;
    }

    /**
     * 回溯的本质就是递归
     */
    public int fib1(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        return fib1(n - 1) + fib1(n - 2);
    }
}
